{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Collect Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #收集元素的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。</p>\n",
    "\n",
    "<p>请你返回收集元素&nbsp;<code>1, 2, ..., k</code>&nbsp;需要的&nbsp;<strong>最少操作次数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,1,5,4,2], k = 2\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>4 次操作后，集合中的元素依次添加了 2 ，4 ，5 和 1 。此时集合中包含元素 1 和 2 ，所以答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,1,5,4,2], k = 5\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>5 次操作后，集合中的元素依次添加了 2 ，4 ，5 ，1 和 3 。此时集合中包含元素 1 到 5 ，所以答案为 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,2,5,3,1], k = 3\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>4 次操作后，集合中的元素依次添加了 1 ，3 ，5 和 2 。此时集合中包含元素 1 到 3  ，所以答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "\t<li>输入保证你可以收集到元素&nbsp;<code>1, 2, ..., k</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-collect-elements](https://leetcode.cn/problems/minimum-operations-to-collect-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-collect-elements](https://leetcode.cn/problems/minimum-operations-to-collect-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,5,4,2]\\n2', '[3,1,5,4,2]\\n5', '[3,2,5,3,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        t=0\n",
    "        while nums[0]!=0:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i]%2!=0:\n",
    "                    nums[i]-=1\n",
    "                    t+=1\n",
    "            for i in range(len(nums)):\n",
    "                nums[i]=nums[i]//2\n",
    "            t+=1\n",
    "        return t-1 if t!=0 else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(31):\n",
    "            Flag = 0\n",
    "            for j in range(n):\n",
    "                ans += nums[j] & 1\n",
    "                nums[j] >>= 1\n",
    "                Flag += nums[j]\n",
    "            ans += 1\n",
    "            if Flag == 0:\n",
    "                return ans - 1\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        while True:\n",
    "            for i in range(n):\n",
    "                if nums[i] % 2 == 1:\n",
    "                    res += 1\n",
    "                nums[i] >>= 1\n",
    "            if sum(nums) == 0:\n",
    "                break\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        while True:\n",
    "            if not any(x > 0 for x in nums):\n",
    "                break\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] % 2:\n",
    "                    res += 1\n",
    "                    nums[i] -= 1\n",
    "\n",
    "            if not any(x > 0 for x in nums):\n",
    "                break\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] //= 2\n",
    "\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums); cnt = 0\n",
    "        while (1):\n",
    "            for i in range(n):\n",
    "                if nums[i] & 1: cnt += 1\n",
    "                nums[i] >>= 1\n",
    "            if sum(nums) == 0: break\n",
    "            cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def help(self, nums):\n",
    "        even = True\n",
    "        step = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] % 2 != 0:\n",
    "                even = False\n",
    "                nums[i] -= 1\n",
    "                step += 1\n",
    "        if even:\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] = nums[i] // 2\n",
    "            step = 1\n",
    "        return nums, step\n",
    "\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 逆向思考如何将nums全部变为0\n",
    "        # 允许两种操作 一种是直接减半 第二种是某个数-1\n",
    "        # 每一步判断如果全是偶数 选择除以2\n",
    "        # 如果存在奇数 该奇数建议变成偶数\n",
    "\n",
    "        # 2 4 5\n",
    "        # 2 4 4\n",
    "        # 1 2 2\n",
    "        # 0 2 2\n",
    "        # 0 1 1\n",
    "        # 0 0 1\n",
    "        # 0 0 0\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while nums.count(0) != n:\n",
    "            nums, step = self.help(nums)\n",
    "            ans += step\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        b=big=0\n",
    "        h=0\n",
    "        for i in nums:\n",
    "            if i>b:\n",
    "                b=i\n",
    "            h+=i.bit_count()\n",
    "        if b==0:return 0\n",
    "        c =-1\n",
    "        while b:\n",
    "            b>>=1\n",
    "            c+=1 \n",
    "        return c+ h\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            for i in range(31):\n",
    "                la[i]+= 1&(n>>i)\n",
    "\n",
    "        #倒序，是关键\n",
    "        j=30 \n",
    "        while j>-1 and la[j]==0:\n",
    "            j-=1\n",
    "        if j<0:return 0\n",
    "        return sum(la)+j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            i=0\n",
    "            while n:\n",
    "                n,yu =divmod(n,2)\n",
    "                la[i]+=yu \n",
    "                i+=1\n",
    "        he =la[0]\n",
    "        f=0\n",
    "        #倒序，是关键\n",
    "        for j in range(30,0,-1):\n",
    "            if f==0 and la[j]>0:\n",
    "                f=1\n",
    "            if f:\n",
    "                he+=la[j]+1\n",
    "        return he"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "      maxVal = 0\n",
    "      cnt = 0\n",
    "      for num in nums:\n",
    "        maxVal = max(num, maxVal)\n",
    "        cnt += num.bit_count()\n",
    "      maxVal >>= 1\n",
    "      while maxVal:\n",
    "        cnt += 1\n",
    "        maxVal >>= 1\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        plus_count = 0\n",
    "        max_multi_count = 0\n",
    "        for i in nums:\n",
    "            binval = bin(i)\n",
    "            length = len(binval) - 2\n",
    "            plus_count += binval.count(\"1\")\n",
    "            if length > 1:\n",
    "                multi_count = length - 1\n",
    "                max_multi_count = max(multi_count, max_multi_count)\n",
    "        return plus_count + max_multi_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums) -> int:\n",
    "        plus_count = 0\n",
    "        max_multi_count = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                continue\n",
    "            val = num\n",
    "            count = 0\n",
    "            while val > 1:\n",
    "                remain = val % 2\n",
    "                val = val >> 1\n",
    "                count += 1\n",
    "                if remain > 0:\n",
    "                    plus_count += 1\n",
    "            if num != 0:\n",
    "                plus_count += 1\n",
    "            max_multi_count = max(max_multi_count, count)\n",
    "        return plus_count + max_multi_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for v in nums:\n",
    "            ans+=v.bit_count()\n",
    "        a=max(nums)\n",
    "        if a==0: return 0\n",
    "        while a:\n",
    "            a=a>>1\n",
    "            ans+=1\n",
    "        return ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        op_2_min = 0  # 第2种操作的最小次数\n",
    "        op_1 = 0  # 第1种操作的次数总数\n",
    "        for num in nums:\n",
    "            op_2 = 0\n",
    "            while num:\n",
    "                if num % 2 == 1:\n",
    "                    num -= 1\n",
    "                    op_1 += 1\n",
    "                else:\n",
    "                    num //= 2\n",
    "                    op_2 += 1\n",
    "            op_2_min = max(op_2_min, op_2)\n",
    "\n",
    "        return op_1 + op_2_min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        max_num = max(nums)\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if num & 1:\n",
    "                    ret += 1\n",
    "                num >>= 1\n",
    "        if max_num  > 0:\n",
    "            while max_num  > 0:\n",
    "                ret += 1\n",
    "                max_num  >>= 1\n",
    "            ret -= 1\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums) -> int:\n",
    "        add_count = 0\n",
    "        chen_count = 0\n",
    "        for num in nums :\n",
    "            if num == 0 :\n",
    "                continue\n",
    "            count = 0\n",
    "            val = num\n",
    "            while val > 1 :\n",
    "                odd = val % 2\n",
    "                val = val >> 1\n",
    "                count += 1\n",
    "                if odd :\n",
    "                    add_count += 1\n",
    "            add_count += 1\n",
    "            chen_count = max(chen_count,count)\n",
    "        return chen_count + add_count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        maxn = max(nums)\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if num & 1:\n",
    "                    ret += 1\n",
    "                num >>= 1\n",
    "        if maxn > 0:\n",
    "            while maxn > 0:\n",
    "                ret += 1\n",
    "                maxn >>= 1\n",
    "            ret -= 1\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for item in nums:\n",
    "            while item>0:\n",
    "                if item%2==1:\n",
    "                    res+=1\n",
    "                item//=2\n",
    "        maxnum = max(nums)\n",
    "        if maxnum>0:\n",
    "            while maxnum>0:\n",
    "                res+=1\n",
    "                maxnum//=2\n",
    "            res-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            i=0\n",
    "            while n:\n",
    "                n,yu =divmod(n,2)\n",
    "                la[i]+=yu \n",
    "                i+=1\n",
    "        #倒序，是关键\n",
    "        j=30 \n",
    "        while j>-1 and la[j]==0:\n",
    "            j-=1\n",
    "        if j==-1:return 0\n",
    "        he=j\n",
    "        for w in range(j,-1,-1):\n",
    "            he+=la[w]\n",
    "        return he"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        maxn = max(nums).bit_length()\n",
    "        return maxn and maxn + sum(maxn.bit_count() for maxn in nums) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        x = max(nums).bit_length()\n",
    "        if (sys.version_info.major, sys.version_info.minor) >= (3, 10):\n",
    "            return x and x + sum(x.bit_count() for x in nums) - 1\n",
    "        else:\n",
    "            return x and x + sum(bin(x).count('1') for x in nums) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            i=0\n",
    "            while n:\n",
    "                n,yu =divmod(n,2)\n",
    "                la[i]+=yu \n",
    "                i+=1\n",
    "        he =la[0]\n",
    "        f=0\n",
    "        #倒序，是关键\n",
    "        j=30 \n",
    "        while la[j]==0:\n",
    "            j-=1\n",
    "            if j==-1:return 0\n",
    "        he=j\n",
    "        for w in range(j,-1,-1):\n",
    "            he+=la[w]\n",
    "        return he"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            for i in range(31):\n",
    "                la[i]+= 1&(n>>i)\n",
    "\n",
    "        #倒序，是关键\n",
    "        j=30 \n",
    "        while j>-1 and la[j]==0:\n",
    "            j-=1\n",
    "        if j==-1:return 0\n",
    "        he=j\n",
    "        for w in range(j,-1,-1):\n",
    "            he+=la[w]\n",
    "        return he"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        div_ = 0 # 除以2的次数\n",
    "        sub_ = 0 # -1的次数\n",
    "        for num in nums:\n",
    "            cur_div = 0\n",
    "            while num:\n",
    "                if num%2==0:\n",
    "                    num //=2\n",
    "                    cur_div += 1\n",
    "                else:\n",
    "                    num -= 1\n",
    "                    sub_ += 1\n",
    "            div_ = max(div_, cur_div)\n",
    "\n",
    "        return div_ + sub_\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        m,ans=0,0\n",
    "        for n in nums:\n",
    "            m=max(n,m)\n",
    "            while n:\n",
    "                if n&1:\n",
    "                    ans+=1\n",
    "                n>>=1\n",
    "        if m: ans-=1\n",
    "        while m:\n",
    "            ans+=1\n",
    "            m>>=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        h=b=big=0\n",
    "        for i in nums:\n",
    "            if i>b:\n",
    "                b=i\n",
    "            h+=i.bit_count()\n",
    "        if b==0:return 0\n",
    "        c =-1\n",
    "        while b:\n",
    "            b>>=1\n",
    "            c+=1 \n",
    "        return c+ h\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # ans = 0\n",
    "        # n = len(nums)\n",
    "        # for i in range(31):\n",
    "        #     Flag = 0\n",
    "        #     for j in range(n):\n",
    "        #         ans += nums[j] & 1\n",
    "        #         nums[j] >>= 1\n",
    "        #         Flag += nums[j]\n",
    "        #     ans += 1\n",
    "        #     if Flag == 0:\n",
    "        #         return ans - 1\n",
    "        # return ans - 1\n",
    "\n",
    "        ans = 0 \n",
    "        maxcount = 0\n",
    "        for i in nums:\n",
    "            count = 0\n",
    "            while i > 0:\n",
    "                ans += i & 1\n",
    "                i >>= 1\n",
    "                count += 1\n",
    "            maxcount = max(maxcount,count)\n",
    "        return max(0,ans + maxcount - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        maxn = max(nums)\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if num & 1:\n",
    "                    ret += 1\n",
    "                num >>= 1\n",
    "        if maxn > 0:\n",
    "            while maxn > 0:\n",
    "                ret += 1\n",
    "                maxn >>= 1\n",
    "            ret -= 1\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = ret = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += (x > 0) + (x - pow(2, bit)) * (x != pow(2, bit))\n",
    "        return (ret + cnt) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def dfs(x):\n",
    "            if x <= 1:\n",
    "                return x\n",
    "            return  x % 2 + dfs(x // 2)\n",
    "        ret = cnt = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += dfs(x)\n",
    "        return (ret + cnt) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums) -> int:\n",
    "        plus_count = 0\n",
    "        max_multi_count = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                continue\n",
    "            val = num\n",
    "            count = 0\n",
    "            while val > 1:\n",
    "                remain = val % 2\n",
    "                val = val >> 1\n",
    "                count += 1\n",
    "                if remain > 0:\n",
    "                    plus_count += 1\n",
    "            plus_count += 1\n",
    "            max_multi_count = max(max_multi_count, count)\n",
    "        return plus_count + max_multi_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = max(nums)\n",
    "        for x in nums:\n",
    "            while x > 0:\n",
    "                if x & 1:\n",
    "                    ans += 1\n",
    "                x >>= 1\n",
    "        if mx > 0:\n",
    "            while mx:\n",
    "                mx >>= 1\n",
    "                ans += 1\n",
    "            ans -= 1\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for v in nums:\n",
    "            ans+=v.bit_count()\n",
    "        a=max(nums)\n",
    "        if a==0: return ans\n",
    "        while a:\n",
    "            ans+=1\n",
    "            a>>=1\n",
    "        return ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = ret = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += (x > 0) + (x - pow(2, bit)) * (x != pow(2, bit))\n",
    "        return (ret + cnt) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def dfs(x):\n",
    "            if x <= 1:\n",
    "                return x\n",
    "            ret = x % 2 + dfs(x // 2)\n",
    "            return ret\n",
    "        ret = cnt = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += dfs(x)\n",
    "        return (ret + cnt) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        maxn = max(nums)\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if num & 1:\n",
    "                    ret += 1\n",
    "                num >>= 1\n",
    "        if maxn > 0:\n",
    "            while maxn > 0:\n",
    "                ret += 1\n",
    "                maxn >>= 1\n",
    "            ret -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        mx = max(nums)\n",
    "\n",
    "        for x in nums:\n",
    "            ans += x.bit_count() \n",
    "\n",
    "        ans += mx.bit_length()-1\n",
    "        return ans if mx  else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 所有数中1比特的数量，加上最长数的位数-1\n",
    "        return sum(i.bit_count() for i in nums) + max(max(nums).bit_length() - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 所有数中1比特的数量，加上最长数的位数-1\n",
    "        ans = sum(i.bit_count() for i in nums) + max(max(nums).bit_length() - 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if (num & 1) == 1:\n",
    "                    result += 1\n",
    "                num = (num >> 1)\n",
    "        maxn = max(nums)\n",
    "        while maxn > 1:\n",
    "            result += 1\n",
    "            maxn = (maxn >> 1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # ans = 0\n",
    "        # n = len(nums)\n",
    "        # for i in range(31):\n",
    "        #     Flag = 0\n",
    "        #     for j in range(n):\n",
    "        #         ans += nums[j] & 1\n",
    "        #         nums[j] >>= 1\n",
    "        #         Flag += nums[j]\n",
    "        #     ans += 1\n",
    "        #     if Flag == 0:\n",
    "        #         return ans - 1\n",
    "        # return ans - 1\n",
    "\n",
    "        # ans = 0 \n",
    "        # maxcount = 0\n",
    "        # for i in nums:\n",
    "        #     count = 0\n",
    "        #     while i > 0:\n",
    "        #         ans += i & 1\n",
    "        #         i >>= 1\n",
    "        #         count += 1\n",
    "        #     maxcount = max(maxcount,count)\n",
    "        # return max(0,ans + maxcount - 1)\n",
    "\n",
    "        ans = 0\n",
    "        maxcount = 0\n",
    "        for i in nums:\n",
    "            temp = bin(i)[2:]\n",
    "            ans += temp.count('1')\n",
    "            maxcount = max(maxcount,len(temp))\n",
    "        return max(0,ans + maxcount - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for num in nums:\n",
    "            binval = bin(num)\n",
    "            l = len(binval) - 2\n",
    "            cnt1 += binval.count('1')\n",
    "            if l > 1:\n",
    "                cnt2 = max(cnt2, l-1)\n",
    "        return cnt1 + cnt2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "      maxVal = 0\n",
    "      cnt = 0\n",
    "      for num in nums:\n",
    "        maxVal = max(num, maxVal)\n",
    "        cnt += num.bit_count()\n",
    "      maxVal >>= 1\n",
    "      while maxVal:\n",
    "        cnt += 1\n",
    "        maxVal >>= 1\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = ret = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += (x > 0) + (x - pow(2, bit)) * (x != pow(2, bit))\n",
    "        return (ret + cnt) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def dfs(x):\n",
    "            if x <= 1:\n",
    "                return x\n",
    "            return x % 2 + dfs(x // 2)\n",
    "        ret = cnt = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += dfs(x)\n",
    "        return ret + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], k: int) -> int:\n",
    "        seen: list[bool] = [False] * (k + 1)\n",
    "        n_left: int = k\n",
    "        i: int = len(nums) - 1\n",
    "        n_ops: int = 0\n",
    "\n",
    "        while n_left > 0:\n",
    "            if nums[i] <= k and not seen[nums[i]]:\n",
    "                seen[nums[i]] = True\n",
    "                n_left -= 1\n",
    "            i -= 1\n",
    "            n_ops += 1\n",
    "        \n",
    "        return n_ops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], k: int) -> int:\n",
    "        visited = set()\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if nums[i]<=k:\n",
    "                visited.add(nums[i])\n",
    "            \n",
    "            if len(visited)==k:\n",
    "                return len(nums)-i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], k: int) -> int:\n",
    "        t=0\n",
    "        res=set()\n",
    "        for c,i in enumerate(nums[::-1]):\n",
    "            if i<=k and i not in res:\n",
    "                res.add(i)\n",
    "                t+=1\n",
    "                if t==k:\n",
    "                    return c+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], k: int) -> int:\n",
    "        t=0\n",
    "        res=set()\n",
    "        for c,i in enumerate(nums[::-1]):\n",
    "            if i<=k and i not in res:\n",
    "                res.add(i)\n",
    "                t+=1\n",
    "                if t==k:\n",
    "                    return c+1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
